<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /* 
    二分搜索的缺陷：二分搜索总是检查 mid 位置上的值，而内插搜索可能会根 据要搜索的值检查数组中的不同地方
    */

    var Arr = [5, 7, 4, 2, 9];

    // 快速排序
    function quickSort(arr){
        const {length} = arr
        if(length < 2){
          return arr
        }
        // 基准值
        let base = arr[0]
        // 拆分以基准值为大小的数组
        let minArr = arr.slice(1).filter(item => item <= base)
        let maxArr = arr.slice(1).filter(item => item > base)
        // 递归调用 并合并数组
        return quickSort(minArr).concat(base).concat(quickSort(maxArr))
      }

    function binarySearch (find, arr, start, end) {
      // 处理第一次 未传入start end的情况
      start = start || 0
      end = end || arr.length - 1

      // 数组排序
      arr = quickSort(arr)

      if (start <= end && find >= arr[start] && find <= arr[end]) {
        // 处理满足条件的情况
        if (find === arr[start]) {
          return start
        }
        if (find === arr[end]) {
          return end
        }

        // 取值的大致位置  向下取整
        const mid = start + Math.floor((find - arr[start]) / (arr[end] - arr[start]) * (end - start))

        if (find === arr[mid]) {
          return mid
        } else if (find > arr[mid]) {
          return binarySearch(find, arr, mid + 1, end)
        } else {
          return binarySearch(find, arr, start, mid - 1)
        }
      }

      return -1

    }
    binarySearch(9, Arr)

  </script>
</body>

</html>